package com.lizk.leetcode.regular;



/**
 * https://leetcode-cn.com/problems/regular-expression-matching/
 * 正则表达式匹配
 * TODO 这个可以使用动态规划的来实现,后面补一下实现的思路
 */
public class Client {
    public static void main(String[] args) {
        Client client = new Client();
        System.out.print(client.isMatch("a",".*"));System.out.println(true);
        System.out.print(client.isMatch("issipp","is*p*"));System.out.println(false);
        System.out.print(client.isMatch("ssissippi","s*is*p*."));System.out.println(false);
        System.out.print(client.isMatch("aaa","ab*a*c*a"));System.out.println(true);
        System.out.print(client.isMatch("a","ab*"));System.out.println(true);
        System.out.print(client.isMatch("abcd",".*e"));System.out.println(false);
        System.out.print(client.isMatch("abcd","e*f*.*"));System.out.println(true);
        System.out.print(client.isMatch("aaa","ab*ac*a"));System.out.println(true);
        System.out.print(client.isMatch("abcd","ab.*d"));System.out.println(true);
        System.out.print(client.isMatch("abcc","abc*"));System.out.println(true);
        System.out.print(client.isMatch("abcd","e*f*abcd"));System.out.println(true);
        System.out.print(client.isMatch("abp",".*p"));System.out.println(true);
        System.out.print(client.isMatch("abp",".*."));System.out.println(true);
        System.out.print(client.isMatch("aa","aa"));System.out.println(true);
        System.out.print(client.isMatch("aa","a"));System.out.println(false);
        System.out.print(client.isMatch("aa","a*"));System.out.println(true);
        System.out.print(client.isMatch("aa",".*"));System.out.println(true);
        System.out.print(client.isMatch("aa","c*a*b"));System.out.println(false);
        System.out.print(client.isMatch("aab","a*b"));System.out.println(true);
        System.out.print(client.isMatch("missis","mis*is"));System.out.println(true);
        System.out.print(client.isMatch("mississippi","mis*is*ip*."));System.out.println(true);
        System.out.print(client.isMatch("mississippi","mis*is*p*."));System.out.println(false);
    }


    /**
     * 动态规划来实现正则匹配
     */
    public boolean isMatch(String s, String p) {
        char[] sArray = s.toCharArray();
        char[] pArray = p.toCharArray();
        boolean [][] result = new boolean[sArray.length+1][pArray.length+1];

        result[0][0] = true;

        for (int i1 = 0; i1 < pArray.length; i1++) {
            if (pArray[i1] == '*'){
                result[0][i1+1] = result [0][i1-1];
            }
        }

        for (int i = 0; i < sArray.length; i++) {
            for (int i1 = 0; i1 < pArray.length; i1++) {
                result[i+1][i1+1] = isMatch(sArray[i],pArray[i1]);
                if (result[i+1][i1+1]){
                    result[i+1][i1+1] = result[i][i1];
                }
                if (pArray[i1] == '*'){
                    if (result[i+1][i1-1]){
                        result[i+1][i1+1] = result[i+1][i1-1];
                    }else{
                        if (isMatch(sArray[i],pArray[i1-1])){
                            result[i+1][i1+1] = result[i][i1+1];
                        }
                    }
                }
            }
        }
        return result[sArray.length][pArray.length];
    }


    public boolean isMatch(char a, char b) {
        if (a == b) return true;
        return b == '.';
    }


    /**
     * 官方答案
     * @return
     */
    public boolean isMatch2(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }


    /**
     * 学习动态规划
     * 用动态规划实现 斐波那契数列
     */
    public int solutionFibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            int result[] = new int[n + 1];
            result[0] = 0;
            result[1] = 1;
            for (int i = 2; i <= n; i++) {
                result[i] = result[i - 1] + result[i - 2];
            }
            return result[n];
        }
    }




}
